package daily.oct;

public class lc3147 {
    public int maximumEnergy(int[] energy, int k) {
        /*
可以从后往前动态规划：
设 dp[i] 表示从房间 i 开始，按照步长 k 能获得的总能量。
转移：
如果 i + k < n，则 dp[i] = energy[i] + dp[i + k]
否则 dp[i] = energy[i]
这样一次遍历就可以得到所有起点的总能量。
取所有 dp[i] 的最大值。
         */
        int n = energy.length;
        int ans = Integer.MIN_VALUE;
        int[] dp = new int[n];

        for (int i = n-1; i >= 0 ; i--) {
            if (i+k<n){
                dp[i] = dp[i+k] + energy[i];
            }else {
                dp[i] = energy[i];
            }

            if (dp[i] > ans){
                ans = dp[i];
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int [] energy = {5,2,-10,-5,1};
        int k = 3;
        lc3147 lc = new lc3147();
        System.out.println(lc.maximumEnergy(energy, k));
    }
}
